2012/01/13

Recent entries from same category

  1. RapidJSON や simdjson よりも速いC言語から使えるJSONライブラリ「yyjson」
  2. コメントも扱える高機能な C++ 向け JSON パーサ「jsoncpp」
  3. C++ で flask ライクなウェブサーバ「clask」書いた。
  4. C++ 用 SQLite3 ORM 「sqlite_orm」が便利。
  5. zsh で PATH に相対パスを含んだ場合にコマンドが補完できないのは意図的かどうか。

追記: 良く見たらstrncpyの罠でもなんでもなく、バッファがクリアされてないのが原因だった。って事であとでpullreqでも送っとくかな。

まぁソート関数自身の問題じゃないので控えめに。

strncpyは必ず \0 で埋めてくれるとは限らない。
404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な

dankogai/c-bucketsort - GitHub

http://blog.livedoor.jp/dankogai/archives/51764911.html
dankogai/c-bucketsort - GitHub

bucketsort - bucket sort that can be used for general purpose

https://github.com/dankogai/c-bucketsort
strncpy(3)のmanページにはこう書いてある。

The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy.

The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

なので... # ./bucketsort README とかするとNULストップしてないバッファで画面が賑やかになり、時にはけたたましいビープ音で心躍る。

サンプルプログラムの仕様が最終行の改行コードなしでも動く様にすべきなのかどうなのかが分からないので diff --git a/main.c b/main.c
index 67e4e00..48391b4 100644
--- a/main.c
+++ b/main.c
@@ -74,6 +74,7 @@ int main(int argc, char **argv)
        if (!lines[lcur])
            EXIT("malloc failed");
        strncpy(lines[lcur], buf, slen - 1);    // do not copy \n
+       lines[lcur][slen - 1] = 0;
     }
     size_t i;
     // for (i = 0; i < lcur; i++) printf("%s\n", lines[i]);
こういうワークアラウンドでもOKなのかもしれないが(そういう点でfork/pullreqはやめた)、おそらくツールとして扱うなら改行コードがあった場合には削除...という動きが望ましいのでstrpbrk(3)やstrchr(3)と使ったり、自作strchrぽい処理を入れていくと他のsortと比較しておられる状況も少し変わったりするのかもしれませんね。確認してないけど。
sort(1)とはやってる事が違いすぎるのでそもそもな気もしなくない。どこを比較したんだろう...。

ちなみに全然オフトピだけど、GNU textutilsに入ってるsort(1)にはコア数によって動的にスレッドを生成してソートする処理が入ってるのでそういうの興味ある人はコード読むといいと思います。
Posted at by